/**
 * Integer to Roman
Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.
 */
package com.xinpan.exercise;

import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedMap;
import java.util.TreeMap;

public class IntegerToRoman {
    public String intToRoman(int num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        SortedMap<Integer, String> dict = new TreeMap<Integer, String>(new Comparator<Integer>(){

			@Override
			public int compare(Integer arg0, Integer arg1) {
				// TODO Auto-generated method stub
				return arg0.intValue() > arg1.intValue() ? -1 :
						(arg0.intValue() == arg1.intValue() ? 0 : 1);
			}
        	
        });
     
        dict.put(1,"I");
        dict.put(4,"IV");
        dict.put(5,"V");
        dict.put(9,"IX");
        dict.put(10,"X");
        dict.put(40,"XL");
        dict.put(50,"L");
        dict.put(90,"XC");
        dict.put(100,"C");
        dict.put(400,"CD");
        dict.put(500,"D");
        dict.put(900,"CM");
        dict.put(1000,"M");
        
        String res = "";
        Iterator<Integer> it = dict.keySet().iterator();
        while(it.hasNext())
        {
        	int val = it.next();
        	while(num >= val)
        	{
        		res += dict.get(val);
        		num -= val;
        	}
        }
        return res;
    }
}
